package com.ly.algorithm.leetcode.linked;

/**
 * @Classname Problem19
 * @Description 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 示例：
 *
 * 给定一个链表: 1.txt->2->3->4->5, 和 n = 2.
 *
 * 当删除了倒数第二个节点后，链表变为 1.txt->2->3->5.
 *
 * @Date 2020/10/18 11:45
 * @Author 冷心影翼
 */
public class Problem19 {

	public static void main(String[] args) {
		Solution19 solution19 = new Solution19();
		ListNode listNode = new ListNode(1);
		listNode.next = new ListNode(2);
		listNode.next.next = new ListNode(3);
		listNode.next.next.next = new ListNode(4);
		listNode.next.next.next.next = new ListNode(5);
//		ListNode node = solution19.removeNthFromEnd(listNode, 2);
		ListNode node2 = solution19.removeNthFromEndBestWay(listNode, 5);
//		System.out.println(node.next.next.next.val);
		System.out.println(node2.val);
		System.out.println(node2.next.val);
		System.out.println(node2.next.next.val);
		System.out.println(node2.next.next.next.val);
	}
}


class Solution19 {
	public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode cur = head;
		int count = 0;
		while (cur != null) {
		    cur = cur.next;
		    count++;
		}

		cur = head;
		n = count - n-1;

		while (n>0) {
			n--;
			cur = cur.next;
		}
		cur.next = cur.next.next;
		return head;
	}


	public ListNode removeNthFromEndBestWay(ListNode head, int n) {
		if(head == null) {
			return null;
		}
		ListNode slow = head;
		ListNode fast = head;

		while (n>0) {
			fast = fast.next;
			n--;
		}
		if(fast == null) {
			return head.next;
		}
		while (fast.next!=null) {
			fast = fast.next;
			slow = slow.next;
		}
		slow.next = slow.next.next;
		return head;
	}
}